package week02

// 433. 最小基因变化
// https://leetcode-cn.com/problems/minimum-genetic-mutation/

func minMutation(start string, end string, bank []string) int {
	var hasResult bool
	for _, str := range bank {
		if str == end {
			hasResult = true
			break
		}
	}
	if !hasResult {
		return -1
	}
	ans := dfs(start, end, make(map[int]bool), bank, 0, []int{})
	return getMin(ans)
}

func dfs(temp string, end string, visit map[int]bool, bank []string, times int, ans []int) []int {
	if temp == end {    // 达成目标，保存变化次数
		return append(ans, times)
	}
	for idx, ban := range bank {
		if visit[idx] {
			continue
		}
		if isDiffOne(temp, ban) {
			visit[idx] = true
			ans = dfs(ban, end, visit, bank, times+1, ans)
			visit[idx] = false
		}
	}
	return ans
}

// 是否相差一个字符
func isDiffOne(temp, bank string) bool {
	var num = 0
	for i := range temp {
		if temp[i] != bank[i] {
			num++
		}
	}
	return num == 1
}

func getMin(ans []int) int {
	if len(ans) == 0 {
		return -1
	}
	var min = 10
	for _, num := range ans {
		if min > num {
			min = num
		}
	}
	return min
}